package cxydmmszl.chapter02.t017;

import java.util.Scanner;

/**
 * <li style="color: red;">Prob</li>
 * 环形单链表的约瑟夫问题
 * <li style="color: red;">Desc</li>
 * 据说著名犹太历史学家 Josephus 有过以下故事：
 * 在罗马人占领乔塔帕特后，39 个犹太人与 Josephus 及他的朋友躲到一个洞中，
 * 39 个犹太人决定宁愿死也不要被敌人抓到，于是决定了一种自杀方式，41 个人排成一个圆圈，
 * 由第 1 个人开始报数，报数到 3 的人就自杀，然后再由下一个人重新报 1，报数到 3 的人再自杀，
 * 这样依次下去，直到剩下最后一个人时，那个人可以自由选择自己的命运。这就是著名的约瑟夫问题。
 * 现在请用单向环形链表得出最终存活的人的编号。<br/><br/>
 * <b>输入描述：</b><br/>
 * 一行两个整数 n 和 m， n 表示环形链表的长度， m 表示每次报数到 m 就自杀。<br/><br/>
 * <b>输出描述：</b><br/>
 * 输出最后存活下来的人编号（编号从 1 开始到 n）
 * <li style="color: red;">Link</li> CD109、CD110
 *
 * @author habitplus
 * @since 2021-08-28 21:20
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Node head = genCycleLinkedList(n);
        Node target = josephusKill01(head, m);
        System.out.println(target == null ? 0 : target.val);
    }

    private static class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public static Node genCycleLinkedList(int n) {

        Node tou = new Node(0), pre = tou, node;
        for (int i = 1; i <= n; i++) {
            node = new Node(i);
            pre.next = node;
            pre = node;
        }
        pre.next = tou.next;

        return tou.next;
    }


    public static Node josephusKill01(Node head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }

        Node pre = head;
        // 让 pre 指向 head 前驱
        while (pre.next != head) {
            pre = pre.next;
        }

        int cnt = 0;
        while (pre != head) {
            if (++cnt == m) {
                pre.next = head.next;
                cnt = 0;
            } else {
                pre = pre.next;
            }
            head = pre.next;
        }

        return head;
    }
}
